/*
    2020年5月18日09:32:06
    设计一个算法删除单链表L(有头结点)中的最小值结点
*/
#define NULL 0

typedef struct Node
{
    int data;
    struct Node *pNext;
} Node, *pList;

//先找到最小值，再查找其结点，很笨的算法
void delmin(pList L)
{
    pList p = L->pNext;
    int min = p->data;
    //找到最小值结点
    while (p->pNext != NULL)
    {
        if (p->data < min)
            min = p->data;
        p = p->pNext;
    }
    pList q = L->pNext;
    //删除最小值结点
    while (q->pNext != NULL)
    {
        if (q->data == min)
        {
            //free(q);
            return;
        }
        q = q->pNext;
    }
}

//再寻找最小值的同时记录其结点，循环后直接删除结点，相比第一种方法，节省了一次循环
void delmin(pList L)
{
    pList p = L;
    pList q;
    int min = p->pNext->data; //min最开始记录第一个结点位置
    while (p != NULL)
    {
        if (p->pNext->data < min)
        {
            min = p->pNext->data;
            q = p->pNext; //q来记录最小值得前驱结点
        }
        p = p->pNext;
    }

    q->pNext = q->pNext->pNext;
    //free(q->pNext);
}

void delmin(pList L)
{
	pList p = L->pNext;
	pList q = NULL;
	int min = p->data;
	//找到最小值结点
	while (p != NULL)
	{
		if (p->data < min)
		{
			min = p->data;
			q = p;
		}
		p = p->pNext;
	}
	//cout << "min data is " << min << endl;
	int temp;
	if (q->pNext != NULL)
	{
		temp = q->data;
		q->data = q->pNext->data;
		q->pNext->data = temp;

		q->pNext = q->pNext->pNext;
	}
	else
	{
		//这个函数不能处理最后一个数据
		//free(q);
		//q = NULL;
	}
}